#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
class Solution
{
  public:
    int mem[N][N];
    int dfs(string &s1, string &s2, int i, int j)
    {
        if (i == 0)
            return j;
        if (j == 0)
            return i;
        if (mem[i][j])
            return mem[i][j];
        if (s1[i - 1] == s2[j - 1])
        {
            return mem[i][j] = dfs(s1, s2, i - 1, j - 1);
        }
        int del = dfs(s1, s2, i - 1, j);
        int ins = dfs(s1, s2, i, j - 1);
        int rep = dfs(s1, s2, i - 1, j - 1);
        return mem[i][j] = 1 + min({del, ins, rep});
    }
    int editDistance(string str1, string str2)
    {
        int n = str1.size();
        int m = str2.size();
        // return dfs(str1, str2, str1.size(), str2.size());

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; i++)
            dp[i][0] = i;
        for (int j = 0; j <= m; j++)
            dp[0][j] = j;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (str1[i - 1] == str2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] =
                        1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
                }
            }
        }
        return dp[n][m];
    }
};